Sejak kemerdekaan Tanah Melayu pada tahun 1957, Pulau Pinang selalu menggunakan versi ringkas lagu kebangsaan, Negaraku, di majlis dan upacara rasmi negeri. Pada 2 Mac 1972, Speaker Dewan Undangan Negeri waktu itu Dato’ Harun Sirat mengumumkan sebuah pertandingan dengan menjemput pengarang dan pemuzik dalam negara untuk mengarang sebuah lagu untuk digunakan sebagai Lagu Negeri Pulau Pinang. Terdapat lebih 40 sertaan memasuki pertandingan itu, tetapi jawatankuasa pertandingan itu hanya menyenarai pendek 10 buah lagu. Panel pengadil kemudiannya mengesyorkan tiga buah lagu kepada kerajaan Negeri untuk pemilihan terakhir pada pada 15 November 1972. Exco Negeri memilih lagu Untuk Negeri Kita daripada tiga sertaan terakhir sebagai Lagu Negeri Pulau Pinang. Lagu ini diperkenalkan dan dimainkan buat kali pertama pada 22 Disember 1972, semasa sambutan hari jadi Gabenor Pulau Pinang, Tun Syed Sheh Hassan Barakbah di Stadium Bandaraya.

Pada asalnya lagu ini dimainkan pada tempo yang lebih perlahan, rentak gubahannya diubah suai pada tahun 1993 untuk menjadi lebih pantas.[4] Tindakan khusus ini yang diumumkan oleh Ketua Menteri ketika itu, Koh Tsu Koon, dikatakan mencerminkan semangat dan dinamisme rakyat Pulau Pinang terhadap kemajuan negeri ini.